package com.straw.jdk.algorithm.sort;

import com.straw.hat.common.util.RandomNumGenerator;

import java.util.Arrays;

/**
 * @company: 鲸灵科技
 * @author: qiyue@webuy.ai
 * @date: 2019/10/10
 * @time: 12:09 上午
 */
public class Sort {



    /**
     *尽量不使用(稳定主要是慢)
     * 冒泡排序算法O(n)-O(n^2)
     * 原理就是从第一个元素开始不断和后面元素比较大小,然后交换位置,直到上一次比较的位置
     * 白话:就是不断把最大的元素完后推
     * @param sourceArray
     */
    public static void bubbleSort(int [] sourceArray){
        int length = sourceArray.length;
        if (length <= 0) {
            return;
        }
        /*循环次数*/
        for (int i = 0 ; i < length ; i ++) {
            /*大的元素不断的向上冒泡*/
            for (int j = 0; j < length-1-i; j++) {
                if (sourceArray[j+1] < sourceArray [j]) {
                    sourceArray[j] = sourceArray[j+1] + sourceArray [j];
                    sourceArray[j+1] =  sourceArray[j] - sourceArray[j+1];
                    sourceArray[j] = sourceArray[j] - sourceArray[j+1];
                }
            }
        }
    }


    /**
     * 不推荐使用(不稳定还慢)
     * 简单选择排序算法O(n)-O(n^2)
     * 白话:就是不断选择小的元素到左侧的尾部
     */
    public static void chooseSort(int [] sourceArray) {
        int length = sourceArray.length;
        if (length <= 0) {
            return;
        }
        /*循环次数*/
        for (int i = 0 ; i < length ; i ++) {
            /*不断的把小的元素放到头部*/
            for (int j = i; j < length; j++) {
                if (sourceArray[i] > sourceArray [j]) {
                    sourceArray[i] = sourceArray[i] + sourceArray[j];
                    sourceArray[j] = sourceArray[i] - sourceArray[j];
                    sourceArray[i] = sourceArray[i] - sourceArray[j];
                }
            }
        }
    }

    /**
     * 优先使用(相对其他2中简单排序稳定较快)
     * 插入排序
     * 白话: 不断将右侧的元素和左侧的元素比较放到合适的位置
     * @param sourceArray
     */
    public static void insertSort(int [] sourceArray) {
        int length = sourceArray.length;
        if (length <= 0) {
            return;
        }
        /*循环次数*/
        for (int i = 0 ; i < length ; i ++) {
            /*不断把小的元素放到左侧排序*/
            for (int j = 0; j < i; j++) {
                if (sourceArray[j] > sourceArray [i]) {
                    sourceArray[i] = sourceArray[i] + sourceArray[j];
                    sourceArray[j] = sourceArray[i] - sourceArray[j];
                    sourceArray[i] = sourceArray[i] - sourceArray[j];
                }
            }
        }
    }


    /**
     * JAVA对象排序使用的就是这种算法CollectionUtils.sort(List<T super Comparator> cmpList)
     *  并归排序(稳定) 把两个排好序的数组组合在一起成为一个新的有序数组
     * @param sourceArray
     */
    public static int [] mergeSort(int [] sourceArray){
        //终止条件
        if (sourceArray.length < 2) {
            return sourceArray;
        }
        /*递归都是从大问题拆解成小问题的,所以拆分成两份*/
        int mid = sourceArray.length / 2;
        int[] left = Arrays.copyOfRange(sourceArray, 0, mid);
        int[] right = Arrays.copyOfRange(sourceArray, mid, sourceArray.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int [] merge(int [] leftArr , int [] rigtArr) {
        int[] result = new int[leftArr.length + rigtArr.length];
        for (int resultIdx = 0, leftIdx = 0, rigtIdx = 0; resultIdx < result.length; resultIdx++) {
            if (leftIdx >= leftArr.length)
                /*左边排好序*/ {
                result[resultIdx] = rigtArr[rigtIdx++];
            } else if (rigtIdx >= rigtArr.length)
                /*右边排好序*/ {
                result[resultIdx] = leftArr[leftIdx++];
            } else if (leftArr[leftIdx] > rigtArr[rigtIdx])
                /*左边的元素大于右边*/ {
                result[resultIdx] = rigtArr[rigtIdx++];
            } else
                /*右边的元素大于左边*/ {
                result[resultIdx] = leftArr[leftIdx++];
            }
        }
        return result;
    }



//    public static int [] quicklySort(int [] sourceArray ,int start , int end) {
//        if (sourceArray == null || sourceArray.length < 1 || start <0 || start > end ) {
//            return sourceArray;
//        }
//        /*选择基准数(参考数,默认都是第一个数字)*/
//        int referenceNumber = sourceArray [start];
//        /*选择左右哨兵*/
//        int leftSentinelIdx = start;
//        int rightSentinelIdx = end;
//        /*循环表示基数数左边和右边的都和基准数比较完成*/
//        while (rightSentinelIdx > leftSentinelIdx ) {
//            /*右边的哨兵开始移动 找到比基准数小的*/
//            while (rightSentinelIdx > leftSentinelIdx && referenceNumber < sourceArray[rightSentinelIdx]) {
//                rightSentinelIdx--;
//            }
//            /*左侧的哨兵开始移动 找到比基准数大的*/
//            while (rightSentinelIdx > leftSentinelIdx && referenceNumber > sourceArray[leftSentinelIdx]) {
//                leftSentinelIdx++;
//            }
//            /*交换哨兵检测出来的两个*/
//            if (rightSentinelIdx > leftSentinelIdx) {
//                sourceArray[leftSentinelIdx] = sourceArray[leftSentinelIdx] + sourceArray[rightSentinelIdx];
//                sourceArray[rightSentinelIdx] = sourceArray[leftSentinelIdx] - sourceArray[rightSentinelIdx];
//                sourceArray[leftSentinelIdx] = sourceArray[leftSentinelIdx] - sourceArray[rightSentinelIdx];
//            }
//
//        }
//        /*将基准数放到中间位置*/
//        sourceArray[leftSentinelIdx] = sourceArray[leftSentinelIdx] + referenceNumber;
//        referenceNumber= sourceArray[leftSentinelIdx] - referenceNumber;
//        sourceArray[leftSentinelIdx] = sourceArray[leftSentinelIdx] - referenceNumber;
//        /*左右区间递归*/
//        quicklySort(sourceArray, start, leftSentinelIdx-1);
//        quicklySort(sourceArray, rightSentinelIdx+1, end);
//        return sourceArray;
//    }

    /**
     * 快速排序(不稳定) 属于是冒泡排序的升级版
     * @param arr
     * @return
     */
    public static void quickSort(int[] arr,int low,int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基准位
        temp = arr[low];

        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j - 1);
        //递归调用右半数组
        quickSort(arr, j + 1, high);
    }





    public static void bucketSort(){




    }




    public static void main(String[] args) {
        int arr [] = RandomNumGenerator.generator(10000000);
        long startTime = System.currentTimeMillis();
        /*1W级别*/
        //cost time : 225微秒 (选择)
        //cost time : 167微秒（冒泡）
        //cost time : 145微秒 (插入)
        //cost time : 3微秒   (快排)
        //cost time : 5微秒   (并归)
        /*10W级别*/
        //cost time : 21631微秒 (选择)
        //cost time : 20959微秒（冒泡）
        //cost time : 16801微秒 (插入)
        //cost time : 21微秒    (快排)
        //cost time : 31微秒    (并归)
        /*100W级别*/
        //cost time : 慢不参与 (选择)
        //cost time : 慢不参与（冒泡）
        //cost time : 慢不参与 (插入)
        //cost time : 159微秒 (快排)
        //cost time : 246微秒 (并归)
        /*1000W级别*/
        //cost time : 慢不参与 (选择)
        //cost time : 慢不参与（冒泡）
        //cost time : 慢不参与 (插入)
        //cost time : 1287微秒(快排)
        //cost time : 2492微秒(并归)
//        chooseSort(arr);
//        bubbleSort(arr);
//        insertSort(arr);
//        quickSort(arr,0,arr.length-1);
//        mergeSort(arr);

        /*总结mergeSort和quickSort是最佳的选择（100W级别几乎无差距）,超大数据量的情况下quick是更好的选择 */
        /*但是quickSort对稳定性支持不好,对稳定性有强制性要求的使用mergeSort*/
        System.out.println("cost time : "+Long.valueOf(System.currentTimeMillis()-startTime) + "微秒");
    }
}
